#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

//void HPSort(int* a, int n)
//{
//	HP hp;
//	//HPInit(&hp);
//	HPInitArrary(&hp, a, n);
//	
//	int i = 0;
//	while (!HPEmpty(&hp))
//	{
//		a[i++] = HPTop(&hp);
//		HPPop(&hp);
//	}
//
//
//	HPDestory(&hp);
//}
//
//int main()
//{
//	int a[] = { 50,100,70,65,60,32 };
//	HPSort(a, sizeof(a) / sizeof(int));
//
//	HP hp;
//	HPInit(&hp);
//	/*for (int i = 0; i < sizeof(a) / sizeof(int); i++)
//	{
//		HPPush(&hp, a[i]);
//	}
//
//	printf("%d\n", HPTop(&hp));
//	HPPop(&hp);
//	printf("%d\n", HPTop(&hp));*/
//
//
//	
//	HPDestory(&hp);
//
//	return 0;
//}

//int main()
//{
//	//int a[] = { 50,100,70,65,60,32 };
//	int a[] = { 60,70,65,50,32,100 };
//
//
//	HP hp;
//	HPInitArray(&hp, a, sizeof(a)/sizeof(int));
//
//	/*HPInit(&hp);
//	for (int i = 0; i < sizeof(a)/sizeof(int); i++)
//	{
//		HPPush(&hp, a[i]);
//	}*/
//
//	//printf("%d\n", HPTop(&hp));
//	//HPPop(&hp);
//	//printf("%d\n", HPTop(&hp));
//	while (!HPEmpty(&hp))
//	{
//		printf("%d\n", HPTop(&hp));
//		HPPop(&hp);
//	}
//
//	HPDestroy(&hp);
//
//	return 0;
//}


// Top-K 问题
void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	// 写数据到文件中
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void TopK()
{
	printf("请输入k:> ");
	int k = 0;
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	int val = 0;
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	// 建k个数的小堆
	for (int i =( k - 1 - 1) / 2; i < k; i++)
	{
		AdjustDown(minheap, k, i);
	}

	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		// 读取剩余数据，比堆顶的值大，就替换它
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	fclose(fout);
}


int main()
{
	CreateNDate();
	TopK();

	return 0;
}